/**
 * @author VernHe
 * @date 2021年07月27日 20:36
 */
public class Temp_02 {
    public static void main(String[] args) {
        Node a = new Node(1);
        a.next = new Node(3);
        a.next.next = new Node(4);

        Node b = new Node(1);
        b.next = new Node(3);
        b.next.next = new Node(5);

        Node c = merge(a,b);
        System.out.println(c == null ? "c为空" : "c不为空");
        while (null != c) {
            System.out.println(c.val);
            c = c.next;
        }
    }

    private static Node merge(Node a, Node b) {
        // 归并排序
        // 定义两个指针分别指向两个链表
        Node p = a;
        Node q = b;
        Node c = null;
        // 初始化c
        if (p.val < q.val) {
            c = p;
            p = p.next;
        } else if (q.val > p.val) {
            c = q;
            q = q.next;
        } else {
            c = p;
            p = p.next;
            q = q.next;
        }
        System.out.println("c初始化后为：" + c.val);
        Node temp = c;
        // 连个链表都没有循环完
        while (p != null && q != null) {
            System.out.println("p当前指向：" + p.val);
            System.out.println("q当前指向：" + q.val);

            // 比较大小
            if (p.val == q.val) {
                temp.next = p;
                // 都往后移动
                p = p.next;
                q = q.next;
                temp = temp.next;
            } else if (p.val < q.val) {
                temp.next = p;
                p = p.next;
                temp = temp.next;
            } else {
                temp.next = q;
                q = q.next;
                temp = temp.next;
            }
            System.out.println("此时temp指向：" + temp.val);
        }
        while (p != null) {
            temp.next = p;
            p = p.next;
            temp = temp.next;
        }
        while (q != null) {
            temp.next = q;
            q = q.next;
            temp = temp.next;
        }
        return c;
    }

    private static class Node {
        private int val;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }
}
